package symbol;

/**
 * description:
 * author:张腾
 * date:2021-04-03
 */

/**
 * 有序符号表  修改符号表的put方法，将每个节点放入符号表时按照一定顺序
 * 用链表实现
 * @param <Key> 键
 * @param <Value> 值
 */
public class OrderSymbolTable<Key extends Comparable,Value> {
    private Node head;
    private int N;

    private class Node{
        public Key key;  //键
        public Value value;  //值
        public Node next;  //下一个节点

        public Node(Key key,Value value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }

    //获取符号表键值对的个数
    public int size(){
        return N;
    }

    //往符号表插入键值对
    public void put(Key key,Value value){
        Node curr = head.next;
        Node pre = head;
        //如果要插入的节点的key小于当前节点的key，则循环，判断下一个节点
        while (curr!=null && key.compareTo(curr.key)>0){
            pre = curr;
            curr = curr.next;
        }
        //如果当前节点curr的键和要插入的key一样，则替换即可
        if (curr!=null && key.compareTo(curr.key)==0){
            curr.value = value;
            return;
        }
        //当前节点curr的键和要插入的key不一样，则把新的节点插入到curr之前
        Node newNode = new Node(key,value,curr);
        pre.next = newNode;

        N++;
    }

    //删除符号表中键为key的键值对
    public void delete(Key key){
        Node n = head;
        while(n!=null){
            if (n.next.key.equals(key)){
                n.next = n.next.next;
                N--;
                return;
            }

            n = n.next;
        }
    }

    //从符号表中获取key对应的值
    public Value get(Key key){
        Node n = head;
        while (n.next!=null){
            n = n.next;
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }

}
